package random;

import java.util.Arrays;

/**
 * 比特位计数
 *
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 */

public class L338 {

    public static void main(String[] args) {

        int[] ints = countBits(5);
        Arrays.stream(ints).forEach(System.out::print);
    }

    public static int[] countBits(int num) {

        if (num == 0) return new int[]{0};
        int[] dp = new int[num + 1];
        for (int i = 1; i < num + 1; i++) {
            // 如果i是奇数，则dp[i] = dp[i>>1]+1; 如果i是偶数，则dp[i] = dp[i>>1]
            dp[i] = (i & 1) != 0 ? dp[i>>1] + 1 : dp[i>>1];
        }
        return dp;
    }

    /*
    官方答案：
    一、直接计算

    二、动态规划——最高有效位
    可以换一个思路，当计算 i 的「一比特数」时，如果存在 0≤j<i，j 的「一比特数」已知，
    且 i 和 j 相比，i 的二进制表示只多了一个 1，则可以快速得到 i 的「一比特数」。
    令 bits[i] 表示 i 的「一比特数」，则上述关系可以表示成：bits[i]=bits[j]+1。

    对于正整数 x，如果可以知道最大的正整数 y，使得y≤x 且 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，
    此时称 y 为 x 的「最高有效位」。令 z=x−y，显然 0≤z<x，则 bits[x]=bits[z]+1。
    为了判断一个正整数是不是 2 的整数次幂，可以利用方法一中提到的按位与运算的性质。
    如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y&(y−1)=0。
    由此可见，正整数 y 是 2 的整数次幂，当且仅当 y&(y−1)=0。

    显然，0 的「一比特数」为 0。使用 highBit 表示当前的最高有效位，遍历从 1 到 num 的每个正整数 i，进行如下操作。
        如果 i&(i−1)=0，则令 highBit=i，更新当前的最高有效位。
        i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个数，因此遍历到 i 时，i−highBit 的「一比特数」已知，
        令 bits[i]=bits[i−highBit]+1。
        最终得到的数组 \textit{bits}bits 即为答案。


    三、动态规划——最低有效位
    这个更简单，更好理解

    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

     */
    public int[] countBits2(int num) {
        int[] bits = new int[num + 1];
        int highBit = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }

    public int[] countBits3(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }


}

